<?php 
/** 
 * 二叉搜索树的后序遍历序列
 * 输入一个整数数组，判断该数组是不是某二叉搜索树的后序遍历的结果。如果是则输出Yes,		否则输出No。假设输入的数组的任意两个数字都互不相同。
 * 二叉搜索树:节点值大于所有的左孩子小于所有的右孩子，以左右孩子为根仍为二分搜索树
 * 
 */



function VerifySquenceOfBST($sequence)
{
    if (!is_array($sequence) || empty($sequence)) {
    	return false;
    }
    $l = 0;
    $r = count($sequence) - 1;
    return judge($sequence, $l, $r);
}

function judge($arr, $l, $r)
{

	$nodeNum = $arr[$r]; // 根节点
	// 搜索左子树
	$i = 0;
	for (;$i < $r; ++ $i) {
		if ($arr[$i] > $nodeNum) { // 找到第一个大于 根节点的数，$i为分界点
			break;
		}
	}

	$j = $i;
	for (;$j < $r; ++$j) { // 查找右子树，如果，右子树中有小于根节点的，返回false
		if ($arr[$j] < $nodeNum) {
			return false;
		}
	}

	//递归判断左子树
	$left = true;
	if ($i > 0) { // 当i > 0 时 说明有左子树
		$left = judge($arr, 0, $i - 1);
	}

	// 递归判断右子树
	$right = true;
	if ($i < $r) {
		$right  = judge($arr, $i, $r - 1);
	}

	return $left && $right;
}

$arr = [1,2,3,5,6,7];
$arr = [9,10,11,13,15,7];
$arr = [10];
$arr = [13,9,10];
$arr = [5,7,6,9,11,10,8];
$arr = [7,4,6,5];
var_dump(VerifySquenceOfBST($arr));
